Á¤º¸°úÇÐȸ ÄÄÇ»ÆÃÀÇ ½ÇÁ¦ ³í¹®Áö (KIISE Transactions on Computing Practices)
Current Result Document :
ÇѱÛÁ¦¸ñ(Korean Title) |
SIMD ±â¹ÝÀÇ VBP ±â¹ýÀ» Àû¿ëÇÑ È¿À²ÀûÀÎ ÄüÁ¤·ÄÀÇ ±¸Çö |
¿µ¹®Á¦¸ñ(English Title) |
An Implementation of Efficient Quicksort Utilizing SIMD-Based VBP Technique |
ÀúÀÚ(Author) |
È«±æ¼®
±èÈ«¿¬
°¼ºÇö
¹ÎÁرâ
Gilseok Hong
Hongyeon Kim
Seonghyeon Kang
Jun-Ki Min
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 23 NO. 08 PP. 0498 ~ 0503 (2017. 08) |
Çѱ۳»¿ë (Korean Abstract) |
SIMD(Single Instruction Multiple Data)´Â ´ëÇ¥ÀûÀÎ º´·ÄÈ ¾ÆÅ°ÅØó Áß Çϳª·Î, SIMD ·¹Áö½ºÅÍ¿¡ ÀûÀçµÈ ¿©·¯ °³ÀÇ µ¥ÀÌÅ͵éÀ» ÇϳªÀÇ ¸í·É¾î·Î ó¸®ÇÏ´Â ±â¼úÀÌ´Ù. ÄüÁ¤·Ä(Quicksort)Àº µ¥ÀÌÅÍ °ªµéÀÌ ¸®½ºÆ®·Î ÀúÀåµÇ¾î ÀÖÀ» ¶§, ÀÓÀÇÀÇ À§Ä¡¿¡ ÀÖ´Â µ¥ÀÌÅÍ °ªÀ» ÇǺ¿À¸·Î ÇÏ¿© ±×°Íº¸´Ù ÀÛÀº °ªÀº ¿ÞÆíÀ¸·Î, Å« °ªÀº ¿À¸¥ÆíÀ¸·Î ºÐÇÒÇÏ¿© »ý¼ºµÈ µÎ °³ÀÇ ¼ºê¸®½ºÆ®¿¡ ´ëÇÏ¿© °°Àº ÀÛ¾÷À» ¹Ýº¹ÇÔÀ¸·Î½á µ¥ÀÌÅÍ °ªµéÀ» Á¤·ÄÇÏ´Â Á¤·Ä ¾Ë°í¸®ÁòÀÌ´Ù. º» ¿¬±¸¿¡¼´Â SIMD ¸í·É¾î¸¦ ÀÌ¿ëÇÏ¿© ÆÄÀÌÇÁ¶óÀÎ ¾ÆÅ°ÅØó¿¡¼ Á¶°Ç ¿¹Ãø ½ÇÆп¡ µû¸¥ ¼º´É ÀúÇϸ¦ À¯¹ßÇÏÁö ¾Êµµ·Ï ºÐ±â Á¶°ÇÀ» ÃÖ¼Ò·Î »ç¿ëÇÏ´Â È¿À²ÀûÀÎ ÄüÁ¤·Ä(Quicksort) ¾Ë°í¸®ÁòÀ» Á¦¾ÈÇÑ´Ù. ¶ÇÇÑ, VBP(Vertical Bit Parallel) ±â¹ý°ú ¾ó¸® ÇÁ·ç´×(early pruning) ±â¹ýÀ» Àû¿ëÇÏ¿© SIMD ·¹Áö½ºÅÍ¿¡ µ¥ÀÌÅ͸¦ ¹ÙÀÌÆ® ´ÜÀ§·Î ÀûÀçÇÔÀ¸·Î½á Äü Á¤·Ä ¾Ë°í¸®ÁòÀÇ ¼º´ÉÀ» Çâ»óÇÏ¿´´Ù.
|
¿µ¹®³»¿ë (English Abstract) |
SIMD (Single Instruction Multiple Data) is a representative parallelization architecture that processes multiple data loaded in a SIMD register with a single instruction. Quicksort is a sorting algorithm that picks an element as a pivot from the array and reorders the array such that all elements having the values less than the pivot value are located in the left side on the pivot as well as all elements having the value greater than the pivot value are located in the right side on the pivot and then the algorithm performs the same task on both sublist recursively. In this paper, we propose an efficient Quicksort algorithm applying the SIMD instructions which minimally invokes conditional branches to avoid the performance degradation incurred by branch misprediction in a pipeline architecture. In addition, we improve the performance of the Quicksort algorithm by fetching data into a SIMD register as a byte unit to apply VBP (Vertical Bit Parallel) and the early pruning technique.
|
Å°¿öµå(Keyword) |
SIMD
VBP
Á¤·Ä
ÄüÁ¤·Ä
SIMD
VBP
sorting
Quicksort
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|